package com.sunny.l18;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.concurrent.LinkedBlockingQueue;

public class Solution {

    HashMap<UndirectedGraphNode, Boolean> used = new HashMap<>();
    /**
     * key 原节点
     * value 新节点
     */
    HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();

    public static void main(String[] args) {

        UndirectedGraphNode node1 = new UndirectedGraphNode(-1);
        UndirectedGraphNode node2 = new UndirectedGraphNode(1);
        node1.neighbors.add(node1);
        node1.neighbors.add(node1);

        Solution solution = new Solution();
        solution.print(node1);

        UndirectedGraphNode newNode1 = solution.cloneGraph(node1);
        solution.print(newNode1);

    }

    public void print(UndirectedGraphNode node){

        LinkedBlockingQueue<UndirectedGraphNode> queue = new LinkedBlockingQueue<>();
        HashMap<UndirectedGraphNode, Boolean> use = new HashMap<>();
        queue.offer(node);
        use.put(node, true);
        while (!queue.isEmpty()){
            UndirectedGraphNode tmp = queue.poll();
            System.out.println(tmp);
            for(UndirectedGraphNode tmpNode: tmp.neighbors){
                if(!use.containsKey(tmpNode)){
                    queue.offer(tmpNode);
                    use.put(tmpNode, true);
                }
            }
        }

    }

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

        if(null == node)
            return null;

        LinkedBlockingQueue<UndirectedGraphNode> queue = new LinkedBlockingQueue<>();
        queue.offer(node);
        used.put(node, true);
        while (!queue.isEmpty()){
            UndirectedGraphNode tmpNode = queue.poll();
            UndirectedGraphNode newNode = new UndirectedGraphNode(tmpNode.label);
            map.put(tmpNode,newNode);
            for(UndirectedGraphNode n: tmpNode.neighbors){
                if(used.containsKey(n)){
                    continue;
                }
                queue.offer(n);
                used.put(n, true);
            }
        }


        queue.clear();
        used.clear();
        queue.offer(node);
        used.put(node, true);
        while (!queue.isEmpty()){
            UndirectedGraphNode tmpNode = queue.poll();
//            System.out.println("********"+tmpNode);
            for(UndirectedGraphNode n: tmpNode.neighbors){
//                System.out.println("&&&&&&&"+n);
                map.get(tmpNode).neighbors.add(map.get(n));
                if(!used.containsKey(n)) {
                    queue.offer(n);
                    used.put(n, true);
                }
            }
        }

        return map.get(node);

    }
}

class UndirectedGraphNode {
    int label;
    ArrayList<UndirectedGraphNode> neighbors;
    UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

    @Override
    public String toString() {
        String res =  "UndirectedGraphNode{" +
                "label=" + label +
                ", neighbors=";
        String content = "";
        for(UndirectedGraphNode node: neighbors){
            content += node.label;
        }
        String tail = "}";
        return res+content+tail;
    }
}
